import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    HashMap<String, Boolean> wordMap = new HashMap<>();
    HashMap<String, Boolean> map = new HashMap<>();
    Queue<String> q = new LinkedList<>();
    char[] temp = new char[26];
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int ret = 1;
        int len = beginWord.length();
        if (beginWord.equals(endWord) || !wordList.contains(endWord)) {
            return 0;
        }

        for (String str : wordList) {
            wordMap.put(str, true);
        }

        q.offer(beginWord);
        map.put(beginWord, true);

        for (int i = 0; i < 26; i++) {
            temp[i] = (char)('a' + i);
        }

        while (!q.isEmpty()) {
            ret++;
            int size = q.size();
            while (size > 0) {
                size--;
                String str = q.poll();
                // ret++;
                for (int i = 0; i < len; i++) {
                    char[] ch = str.toCharArray();
                    for (int j = 0; j < 26; j++) {
                        ch[i] = temp[j];
                        String s = new String(ch);
                        if (s.equals(endWord)) {
                            return ret;
                        }
                        if (wordMap.containsKey(s) && !map.containsKey(s)) {
                            q.offer(s);
                            map.put(s, true);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
